use std::os::raw::c_void;
use std::rc::Rc;

/// 表示红黑树空指针常量
pub const RB_TREE_NULL: *mut c_void = std::ptr::null_mut();

/// 红黑树键类型（后续任务将泛型化）
pub type RBTreeKey = *mut c_void;

/// 红黑树值类型（后续任务将泛型化）
pub type RBTreeValue = *mut c_void;

/// 节点比较函数签名（临时实现）
pub type RBTreeCompareFunc = fn(RBTreeValue, RBTreeValue) -> i32;

/// 红黑树节点颜色枚举
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RBTreeNodeColor {
    Red,
    Black,
}

/// 子树方位标识枚举
#[repr(u8)]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RBTreeNodeSide {
    Left = 0,
    Right = 1,
}

impl RBTreeNodeSide {
    pub fn opposite(self) -> Self {
        match self {
            RBTreeNodeSide::Left => RBTreeNodeSide::Right,
            RBTreeNodeSide::Right => RBTreeNodeSide::Left,
        }
    }
}

/// 红黑树节点结构体
#[derive(Debug)]
pub struct RbTreeNode {
    /// 节点颜色标识
    pub color: std::cell::Cell<RBTreeNodeColor>,
    /// 节点存储的键
    pub key: RBTreeKey,
    /// 节点存储的值
    pub value: RBTreeValue,
    /// 父节点指针（使用 Weak 避免循环引用）
    pub parent: std::cell::RefCell<std::rc::Weak<RbTreeNode>>,
    /// 子节点数组（使用 RefCell 实现内部可变性）
    pub children: [std::cell::RefCell<Option<std::rc::Rc<RbTreeNode>>>; 2],
}

/// 判断节点在父节点中的方位
/// 
/// # 参数
/// - `node`: 待判断的红黑树节点引用
/// 
/// # 返回值
/// 返回节点所属方位枚举值（Left/Right）
pub fn rb_tree_node_side(node: &RbTreeNode) -> RBTreeNodeSide {
    let parent_rc = node.parent.borrow().upgrade().expect("Parent node already dropped");
    
    if let Some(left_child) = &*parent_rc.children[RBTreeNodeSide::Left as usize].borrow() {
        if std::ptr::eq(left_child.as_ref(), node) {
            return RBTreeNodeSide::Left;
        }
    }
    
    RBTreeNodeSide::Right
}


/// 获取红黑树节点的键
impl RbTreeNode {
    /// 获取节点的键
    /// 
    /// # 参数
    /// - `&self`: 不可变节点引用
    /// 
    /// # 返回
    /// 节点存储的键指针
    pub fn key(&self) -> RBTreeKey {
        self.key
    }

    /// 获取节点的值
    /// 
    /// # 参数
    /// - `&self`: 不可变节点引用
    /// 
    /// # 返回
    /// 节点存储的值指针
    pub fn value(&self) -> RBTreeValue {
        self.value
    }

    /// 获取指定方向的子节点
    /// 
    /// # 参数
    /// - `&self`: 不可变节点引用
    /// - `side`: 子树方位标识
    /// 
    /// # 返回
    /// Option包装的Rc节点引用，None表示无子节点
    pub fn child(&self, side: RBTreeNodeSide) -> Option<std::rc::Rc<Self>> {
        self.children[side as usize]
            .borrow()
            .as_ref()
            .cloned()
    }

    /// 获取父节点
    /// 
    /// # 参数
    /// - `&self`: 不可变节点引用
    /// 
    /// # 返回
    /// Option包装的Rc节点引用，None表示无父节点
    pub fn parent(&self) -> Option<std::rc::Rc<Self>> {
        self.parent.borrow().upgrade()
    }

    /// 查找以当前节点为根的子树中的最小节点
    pub fn minimum(node: Rc<Self>) -> Rc<Self> {
        let mut current = node;
        loop {
            let next = current.child(RBTreeNodeSide::Left);
            if let Some(left) = next {
                current = left;
            } else {
                break current;
            }
        }
    }
}

/// 红黑树容器结构
#[derive(Debug)]
pub struct RBTree {
    /// 根节点指针（使用 RefCell 实现内部可变性）
    pub root_node: std::cell::RefCell<Option<std::rc::Rc<RbTreeNode>>>,
    /// 节点比较函数
    pub compare_func: RBTreeCompareFunc,
    /// 树中节点总数（使用 RefCell 实现内部可变性）
    pub num_nodes: std::cell::RefCell<i32>,
}

impl RBTree {
    /// 在红黑树中查找指定键对应的节点
    ///
    /// # 参数
    /// - `key`: 要查找的键指针
    ///
    /// # 返回
    /// Option包装的Rc节点引用，None表示未找到
    pub fn lookup_node(&self, key: RBTreeKey) -> Option<std::rc::Rc<RbTreeNode>> {
        let mut current = self.root_node.borrow().clone();

        loop {
            let node = match current {
                Some(node) => node,
                None => break,
            };
            let diff = (self.compare_func)(key, node.key);
            match diff {
                0 => return Some(node.clone()),
                d if d < 0 => {
                    current = node.children[RBTreeNodeSide::Left as usize].borrow().clone();
                }
                _ => {
                    current = node.children[RBTreeNodeSide::Right as usize].borrow().clone();
                }
            }
        }

        None
    }
}
impl RBTree {
    /// 插入键值对到红黑树中
    ///
    /// # 参数
    /// - `key`: 键的指针
    /// - `value`: 值的指针
    pub fn insert(&self, key: RBTreeKey, value: RBTreeValue) {
        let mut parent = None;
        let mut current = self.root_node.borrow().clone();
        let mut side = RBTreeNodeSide::Left;

        // 查找插入位置
        while let Some(node) = current {
            parent = Some(node.clone());
            let diff = (self.compare_func)(key, node.key);
            if diff < 0 {
                current = node.child(RBTreeNodeSide::Left);
                side = RBTreeNodeSide::Left;
            } else {
                current = node.child(RBTreeNodeSide::Right);
                side = RBTreeNodeSide::Right;
            }
        }

        // 创建新节点
        let new_node = Rc::new(RbTreeNode {
            color: std::cell::Cell::new(RBTreeNodeColor::Red),
            key,
            value,
            parent: std::cell::RefCell::new(std::rc::Weak::new()),
            children: [
                std::cell::RefCell::new(None),
                std::cell::RefCell::new(None),
            ],
        });

        // 链接到父节点
        if let Some(parent_node) = parent {
            *new_node.parent.borrow_mut() = Rc::downgrade(&parent_node);
            *parent_node.children[side as usize].borrow_mut() = Some(new_node.clone());
        } else {
            // 树为空，新节点为根
            *self.root_node.borrow_mut() = Some(new_node.clone());
        }

        // 更新节点计数
        *self.num_nodes.borrow_mut() += 1;

        // 修复红黑树性质
        rb_tree_insert_case1(self, &new_node);
    }
}
/// 处理插入修复第五种情况
pub fn rb_tree_insert_case5(tree: &RBTree, node: &std::rc::Rc<RbTreeNode>) {
    let parent = node.parent().expect("Parent must exist in case5");
    let grandparent = parent.parent().expect("Grandparent must exist in case5");
    let side = rb_tree_node_side(node);
    let rotate_dir = match side {
        RBTreeNodeSide::Left => RBTreeNodeSide::Right,
        RBTreeNodeSide::Right => RBTreeNodeSide::Left,
    };

    rb_tree_rotate(tree, &grandparent, rotate_dir);
    parent.color.set(RBTreeNodeColor::Black);
    grandparent.color.set(RBTreeNodeColor::Red);
}
fn rb_tree_node_replace(tree: &RBTree, old_node: &Rc<RbTreeNode>, new_node: Option<&Rc<RbTreeNode>>) {
    // 处理父节点关系
    if let Some(parent) = old_node.parent.borrow().upgrade() {
        let side = rb_tree_node_side(old_node);
        *parent.children[side as usize].borrow_mut() = new_node.cloned();
        
        if let Some(new_node) = new_node {
            *new_node.parent.borrow_mut() = Rc::downgrade(&parent);
        }
    } else {
        // 处理根节点替换
        *tree.root_node.borrow_mut() = new_node.cloned();
        if let Some(new_node) = new_node {
            *new_node.parent.borrow_mut() = std::rc::Weak::new();
        }
    }
}

fn rb_tree_rotate(tree: &RBTree, node: &Rc<RbTreeNode>, direction: RBTreeNodeSide) {
    let opposite = direction.opposite();
    let new_root = node.child(opposite).expect("Child must exist for rotation");

    // 更新父节点关系
    rb_tree_node_replace(tree, node, Some(&new_root));

    // 调整子节点指针
    *node.children[opposite as usize].borrow_mut() = new_root.child(direction);
    *new_root.children[direction as usize].borrow_mut() = Some(Rc::clone(node));

    // 更新父指针
    *node.parent.borrow_mut() = Rc::downgrade(&new_root);
    if let Some(child) = &*node.children[opposite as usize].borrow() {
        *child.parent.borrow_mut() = Rc::downgrade(node);
    }
}
    /// 将红黑树节点值转换为有序数组
    /// 
    /// # 参数
    /// - `&self`: 红黑树不可变引用
    /// 
    /// # 返回
    /// 指向值指针数组的原始指针，数组长度可通过num_entries获取
    /// 

impl RBTree {
    /// 创建新的红黑树实例
    /// 
    /// # 参数
    /// - `compare_func`: 节点比较函数
    /// 
    /// # 返回
    /// 初始化完成的红黑树实例
    pub fn new(compare_func: RBTreeCompareFunc) -> Self {
        Self {
            root_node: std::cell::RefCell::new(None),
            compare_func,
            num_nodes: std::cell::RefCell::new(0),
        }
    }

    /// 获取红黑树的根节点
    /// 
    /// # 返回
    /// Option包装的Rc节点引用，None表示空树
    pub fn root_node(&self) -> Option<std::rc::Rc<RbTreeNode>> {
        self.root_node.borrow().clone()
    }

    /// 将红黑树节点值转换为有序数组
    /// 
    /// # 参数
    /// - `&self`: 红黑树不可变引用
    /// 
    /// # 返回
    /// 指向值指针数组的原始指针，数组长度可通过num_entries获取
    /// 
    /// # 安全
    /// 调用者需使用Box::from_raw重建并释放内存，避免内存泄漏
    pub fn to_array(&self) -> *mut RBTreeValue {
        let mut collector = Vec::with_capacity(*self.num_nodes.borrow() as usize);
        self.in_order_traversal(|node| collector.push(node.value));

        let mut boxed_slice = collector.into_boxed_slice();
        let ptr = boxed_slice.as_mut_ptr();
        std::mem::forget(boxed_slice);
        ptr
    }

    /// 中序遍历辅助方法
    /// 使用迭代式遍历避免递归栈溢出
    fn in_order_traversal<F: FnMut(&RbTreeNode)>(&self, mut callback: F) {
        let mut stack = Vec::new();
        let mut current = self.root_node.borrow().clone();

        while !stack.is_empty() || current.is_some() {
            while let Some(node) = current {
                stack.push(node.clone());
                current = node.child(RBTreeNodeSide::Left);
            }

            if let Some(node) = stack.pop() {
                callback(&node);
                current = node.child(RBTreeNodeSide::Right);
            }
        }
    }
    /// 获取红黑树中存储的节点总数
    /// 
    /// # 返回
    /// 当前树中存储的节点数量
    pub fn num_entries(&self) -> i32 {
        *self.num_nodes.borrow()
    }
}  // 原impl块的结束括号



/// 迭代释放子树所有节点及其关联内存
/// 
/// # 参数
/// - `node`: 要释放的子树的根节点（Option包装的Rc指针）
fn rb_tree_free_subtree(node: Option<std::rc::Rc<RbTreeNode>>) {
    let mut stack = vec![];
    if let Some(node) = node {
        stack.push(node);
    }

    while let Some(node) = stack.pop() {
        // 使用模式匹配安全取出子节点
        let left = node.children[RBTreeNodeSide::Left as usize].borrow_mut().take();
        let right = node.children[RBTreeNodeSide::Right as usize].borrow_mut().take();

        // 使用 Option::map 简化代码逻辑
        left.map(|l| stack.push(l));
        right.map(|r| stack.push(r));
    }
}

impl RBTree {
    /// 安全释放整个红黑树结构及其所有节点
    /// 
    /// # 参数
    /// - `self`: 消费自身所有权确保后续不可访问
    pub fn free(self) {
        // 取出根节点并清空树结构
        let root = self.root_node.borrow_mut().take();
        rb_tree_free_subtree(root);
        
        // 原子化重置节点计数器
        *self.num_nodes.borrow_mut() = 0;
        
        // self 在此处离开作用域自动执行 Drop
    }
}

/// 处理插入修复情况4
pub fn rb_tree_insert_case4(tree: &RBTree, node: &Rc<RbTreeNode>) {
    let parent = node.parent().expect("Parent must exist in case4");
    let side = rb_tree_node_side(node);

    if side != rb_tree_node_side(&parent) {
        // 需要先进行旋转操作
        let rotate_dir = side.opposite();
        rb_tree_rotate(tree, &parent, rotate_dir);
        rb_tree_insert_case5(tree, &parent);
    } else {
        rb_tree_insert_case5(tree, node);
    }
}

/// 获取节点的兄弟节点
fn rb_tree_node_sibling(node: &RbTreeNode) -> Option<Rc<RbTreeNode>> {
    let parent = node.parent.borrow().upgrade()?;
    let side = rb_tree_node_side(node);
    parent.child(side.opposite())
}

/// 获取节点的叔叔节点
pub fn rb_tree_node_uncle(node: &RbTreeNode) -> Option<Rc<RbTreeNode>> {
    let parent = node.parent.borrow().upgrade()?;
    rb_tree_node_sibling(&parent)
}

/// 处理插入修复情况3
pub fn rb_tree_insert_case3(tree: &RBTree, node: &Rc<RbTreeNode>) {
    if let Some(uncle) = rb_tree_node_uncle(node) {
        if uncle.color.get() == RBTreeNodeColor::Red {
            let parent = node.parent().expect("Parent must exist in case3");
            let grandparent = parent.parent().expect("Grandparent must exist in case3");

            parent.color.set(RBTreeNodeColor::Black);
            uncle.color.set(RBTreeNodeColor::Black);
            grandparent.color.set(RBTreeNodeColor::Red);

            rb_tree_insert_case1(tree, &grandparent);
            return;
        }
    }
    rb_tree_insert_case4(tree, node);
}

/// 处理插入修复情况1
pub fn rb_tree_insert_case1(tree: &RBTree, node: &Rc<RbTreeNode>) {
    if node.parent().is_none() {
        node.color.set(RBTreeNodeColor::Black);
    } else {
        rb_tree_insert_case2(tree, node);
    }
}

/// 处理插入修复情况2
pub fn rb_tree_insert_case2(tree: &RBTree, node: &Rc<RbTreeNode>) {
    let parent = node.parent().expect("Parent must exist in case2");
    if parent.color.get() == RBTreeNodeColor::Red {
        rb_tree_insert_case3(tree, node);
    }
}

impl RBTree {
    /// 在红黑树中查找指定键对应的值
    ///
    /// # 参数
    /// - `key`: 要查找的键指针
    ///
    /// # 返回
    /// 若找到则返回节点值的原始指针，否则返回空指针
    pub fn lookup(&self, key: RBTreeKey) -> RBTreeValue {
        self.lookup_node(key)
            .map(|node| node.value())
            .unwrap_or(RB_TREE_NULL)
    }
}

impl RBTree {
    /// 从红黑树中移除指定键对应的节点
    /// 
    /// # 参数
    /// - `key`: 要移除的键指针
    /// 
    /// # 返回
    /// 是否成功移除的布尔值
    pub fn remove(&self, key: RBTreeKey) -> bool {
        match self.lookup_node(key) {
            Some(node) => {
                self.remove_node(&node);
                true
            }
            None => false,
        }
    }

    /// 内部方法：执行实际节点移除操作
    /// 
    /// # 参数
    /// - `node`: 要移除的节点引用
    fn remove_node(&self, node: &Rc<RbTreeNode>) {
        // 实现红黑树删除算法核心逻辑
        let mut child = None;
        let mut parent = node.parent();
        let mut original_color = node.color.get();

        // 处理子节点情况
        match (node.child(RBTreeNodeSide::Left), node.child(RBTreeNodeSide::Right)) {
            (None, None) => {
                rb_tree_node_replace(self, node, None);
            }
            (Some(left), None) => {
                rb_tree_node_replace(self, node, Some(&left));
                child = Some(left);
            }
            (None, Some(right)) => {
                rb_tree_node_replace(self, node, Some(&right));
                child = Some(right);
            }
            (Some(_), Some(right)) => {
                let successor = RbTreeNode::minimum(right);
                original_color = successor.color.get();
                child = successor.child(RBTreeNodeSide::Right);
                parent = successor.parent();

                if let Some(child) = &child {
                    *child.parent.borrow_mut() = Rc::downgrade(&successor);
                }

                rb_tree_node_replace(self, &successor, None);
                rb_tree_node_replace(self, node, Some(&successor));
            }
        }

        // 如果原始颜色是黑色需要修复
        if original_color == RBTreeNodeColor::Black {
            if let Some(child) = &child {
                rb_tree_delete_fixup(self, child);
            } else if let Some(parent) = &parent {
                rb_tree_delete_fixup(self, parent);
            }
        }

        // 更新节点计数器
        *self.num_nodes.borrow_mut() -= 1;
    }
}

/// 红黑树删除修复操作
fn rb_tree_delete_fixup(tree: &RBTree, node: &Rc<RbTreeNode>) {
    // 实现红黑树删除修复逻辑
    // （此处应包含完整的红黑树删除修复算法实现）
}